package com.isaiah.list;

/**
 * @Title: 双向链表
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/5/1216:52
 */
public class DoubleLinkedList<E> {

    /**
     * 定义节点类型
     */
    private class Node{
        /** 数据元素 */
        public E e;
        /**  指向上一个节点的指针 */
        public Node prev;
        /**  指向下一个节点的指针 */
        public Node next;

        public Node(E e) {
            this.e = e;
            this.prev = null;
            this.next = null;

        }

        public Node(E e, Node prev, Node next) {
            this.e = e;
            this.prev = prev;
            this.next = next;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }
    /** 头节点 */
    private Node head;

    /** 元素个数 */
    private int size;

    /**
     * 获取链表中的元素个数
     * @return
     */
    public int getSize(){
        return this.size;
    }

    /**
     * 链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return this.size == 0;
    }


    /**
     * 在链表头部添加节点
     * @param e
     */
    public void addFirst(E e){
        // 1. 创建节点
        Node node = new Node(e);
        // 2. 新节点指向原来的头节点
        node.next = head;
        // 3. 头节点重新指向现在的新节点，即现在的新节点成为头节点
        head = node;
        // 4. 维护size加1
        size ++;
    }

    /**
     * 在链表指定位置添加元素
     * @param index
     * @param e
     */
    public void add(int index, E e){
        // 判断index参数是否合法
        if (index <=0 || index > size){
            new IllegalArgumentException("Add element failed, Require index >=0 and index < size");
        }
        if (index == 0){
            addFirst(e);
        }else{
            // 1. 从头节点遍历链表节点，直到index位置为止
            Node pre = head;
            for (int i =0; i < index; i++){
                pre = pre.next;
            }
            // 2. 创建新节点, 新节点的next指向当前节点的next
            Node node = new Node(e);
            node.next = pre.next;
            node.prev = pre.prev;
            // 3. 当前节点的next指向新节点
            pre.next = node;
            pre.prev = node;
            // 3. 维护size加1
            size ++;
        }
    }

    /**
     * 在链表的末尾添加元素
     * @param e
     */
    public void addLast(E e){
        // 调用add方法在size位置添加一个元素，即在链表的末尾添加元素
        this.add(size, e);
    }

    @Override
    public String toString() {
        StringBuffer rs = new StringBuffer();
        Node current = this.head.next;
        while (current != null){
            rs.append(current + "->");
            current = current.next;
        }
        rs.append("NULL");
        return rs.toString();
    }
}
